package io.github.hadyang.leetcode.random;

import com.google.common.collect.Lists;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.function.Function;

/**
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 *
 * <p>说明：
 *
 * <p>拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1：
 *
 * <p>输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成
 * "leet code"。 示例 2：
 *
 * <p>输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple"
 * 可以被拆分成 "apple pen apple"。   注意你可以重复使用字典中的单词。 示例 3：
 *
 * <p>输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author haoyang.shi
 * @date 2019-10-20
 */
public class Q139 {
  public boolean wordBreak(String s, List<String> wordDict) {
    if (wordDict.contains(s)) return true;

    int maxWordLen = 0;
    for (String word : wordDict) {
      maxWordLen = Math.max(maxWordLen, word.length());
    }

    boolean[] p = new boolean[s.length() + 1];
    p[0] = true;

    for (int i = 1; i <= s.length(); i++) {
      for (int j = 0; j <= i; j++) {
        if (p[j] && wordDict.contains(s.substring(j, i))) {
          p[i] = true;
          break;
        }
      }
    }

    return p[s.length()];
  }

  @Test
  public void test() {
    List<String> dict = Lists.newArrayList("leet", "code");
    System.out.println(wordBreak("leetcode", dict));

    dict = Lists.newArrayList("apple", "pen");
    System.out.println(wordBreak("applepenapple", dict));

    dict = Lists.newArrayList("cats", "dog", "sand", "and", "cat");
    System.out.println(wordBreak("catsandog", dict));

    dict = Lists.newArrayList("aaaa", "aaa");
    System.out.println(wordBreak("aaaaaaaa", dict));
  }
}
